# -*- encoding: utf-8 -*-
'''
Filename         :33_search.py
Description      :
Time             :2022/08/23 16:54:31
Author           :daiyizheng
Email            :387942239@qq.com
Version          :1.0
'''

from typing import List


class Solution:
    ## 使用二分搜索
    # 思路：如果中间的数小于最右边的数，则右半段是有序的，
    # 若中间数大于最右边数，则左半段是有序的，
    # 我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内，
    # 这样就可以确定保留哪半边了
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        l, r = 0, len(nums) - 1
        while l<=r: ##考虑边界条件
            mid = l+(r-l)//2
            if nums[mid]==target: return mid
            if nums[0]<=nums[mid]: ## 因为是升序的，说明左边的是有序，包括mid正好在0上
                if nums[l]<= target< nums[mid]:           # 判断target 是否在[l, mid]中
                    r = mid-1
                else:
                    l = mid+1
            else:  ## 说明右边是有序的
                if  nums[mid] <target<=nums[r]: #判断右边是否有target
                    l = mid+1
                else:
                    r = mid-1
        return -1
if __name__ == '__main__':
    Solution().search([4,5,6,1,2,3], target=5)